package own.stu.jobgib.playown.alg.leetcode.editor.cn;


import org.redisson.Redisson;
import org.redisson.api.RLock;
import org.redisson.api.RedissonClient;
import org.redisson.config.Config;

import java.util.*;
import java.util.concurrent.TimeUnit;

public class Solution {

    public static void main(String[] args) throws Exception {
        Solution s = new Solution();

        /*Config config = new Config();
        config.useSingleServer()
                .setConnectionMinimumIdleSize(4)
                .setSubscriptionConnectionMinimumIdleSize(4)
                .setAddress("redis://127.0.0.1:6379");

        RedissonClient client = Redisson.create(config);
        RLock lock = client.getLock("sss");
        try {
            lock.lock();
            System.out.println(" ------ ");
            TimeUnit.MINUTES.sleep(20);
        } finally {
            lock.unlock();
        }*/

        /*RQueue<Object> queue = client.getQueue("q-1");
        System.out.println(" ========= " + queue.add("sss"));
//        TimeUnit.MINUTES.sleep(20);
        queue.delete();
        client.shutdown();*/


        System.out.println(s.numSubarrayProductLessThanK(new int[]{10, 5, 2, 6}, 38));
    }

    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if(nums == null || nums.length == 0 || k <= 0){
            return 0;
        }
        int res = 0;
        int len = nums.length;

        long multi = 1L;
        int i = 0, j = 0;
        for(i = 0; i < len; i ++){
            while(j < len && multi * nums[j] < k){
                multi *= nums[j];
                j ++;
                res ++;
            }

            if(i < j && multi / nums[i] < k){
                multi /= nums[i];
                res ++;
            }
        }

        return res;
    }
    public static void testTreeSet() {

        TreeSet<Integer> set = new TreeSet<>();
        set.add(1);
        set.add(4);
        set.add(7);
        set.add(9);

        System.out.println(set.ceiling(5));
        System.out.println(set.floor(5));

        System.out.println(set.ceiling(0));
        System.out.println(set.floor(0));

        System.out.println(set.ceiling(10));
        System.out.println(set.floor(10));

    }

    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> ans = new ArrayList<>();
        if (n <= 0 || k <= 0 || n < k) {
            return ans;
        }

        helper(ans, n, k, 1, new ArrayList<Integer>());

        return ans;
    }

    private void helper(List<List<Integer>> ans, int n, int k, int idx, List<Integer> list) {
        if (k <= 0) {
            if (k == 0) {
                ans.add(new ArrayList<>(list));
            }
            return;
        }

        int len = n - k + 1;
        for (int i = idx; i <= len; i++) {
            list.add(i);
            helper(ans, n, k - 1, i + 1, list);
            list.remove(list.size() - 1);
        }
    }

    public int findTargetSumWays(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int sumMax = 0;
        for (int i : nums) {
            sumMax += i;
        }
        if (sumMax < target || -sumMax > target) {
            return 0;
        }
        helper(nums, 0, target, 0);
        return ans;
    }

    private void helper(int[] nums, int idx, int target, int sum) {
        if (idx == nums.length) {
            if (target == sum) {
                ans++;
            }
            return;
        }

        helper(nums, idx + 1, target, sum - nums[idx]);
        helper(nums, idx + 1, target, sum + nums[idx]);
    }

    int ans = 0;

    public int longestAlternatingSubarray(int[] nums, int threshold) {
        if (nums == null || nums.length == 0 || threshold <= 0) {
            return 0;
        }
        int n = nums.length;
        int l = 0, r = 0;
        int ans = 0;
        int idx = 0;
        while (idx < n) {
            if (idx < n && (nums[idx] & 1) == 0 && nums[idx] <= threshold) {
                l = idx;
            } else {
                idx++;
                continue;
            }

            r = l;
            if (r == n) {
                return Math.max(ans, 1);
            }
            while (r < n && nums[r] <= threshold
                    && r + 1 < n && nums[r + 1] <= threshold
                    && nums[r] % 2 != nums[r + 1] % 2) {
                r++;
            }
            ans = Math.max(ans, r - l + 1);
            idx = r + 1;
        }

        return ans;
    }

    private static int base = 131, mod = (int) (1e9 + 7);

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        if ((root.val < p.val && root.val > q.val) || (root.val > p.val && root.val < q.val)) {
            return root;
        }
        if (root.val < p.val) {
            return lowestCommonAncestor(root.right, p, q);
        } else {
            return lowestCommonAncestor(root.left, p, q);
        }
    }

    public int numRollsToTarget(int n, int k, int target) {
        if (n <= 0 || k <= 0 || target <= 0) {
            return 0;
        }

        // TODO
        return 1;
    }

    public int subarraySum_iii(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int pre = 0;
        int ans = 0;
        for (int num : nums) {
            if (pre == k) {
                ans++;
                pre = num;
            } else {
                pre += num;
            }
        }
        return ans;
    }

    public int subarraySum(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
         /*
        题目要求连续子数组，因此不能把nums排序，数据规模为10^4 ,时间复杂度应该为o(n)
        可以使用滑动窗口 不行，边界不好处理
        前缀和 + map
        */
        Map<Integer, Integer> map = new HashMap<>(); // preSum : cnt
        map.put(0, 1);
        int pre = 0;
        int n = nums.length;
        int ans = 0;

        for (int i = 0; i < n; i++) {
            pre += nums[i];
            ans += map.getOrDefault(pre - k, 0);
            map.put(pre, map.getOrDefault(pre, 0) + 1);
        }
        return ans;
    }


    public boolean stoneGame(int[] piles) {
        if (piles == null || piles.length == 0) {
            return false;
        }
        /*
        dp[i][j]表示区间（i，j)的对于先手来说的最大差值
        // len = 1
        dp[i][i] = p[i]
        len =2
        dp[i][j] = Max(-dp[i + 1][j]  + v[i], -dp[i][j - 1] + v[j])

        res dp[0][n - 1] > 0
         */
        int n = piles.length;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            dp[i][i] = piles[i];
        }
        // len = 2..n
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i < n - len + 1; i++) {
                int j = i + len - 1;
                dp[i][j] = Math.max(-dp[i + 1][j] + piles[i], -dp[i][j - 1] + piles[j]);
            }
        }
        return dp[0][n - 1] > 0;
    }

    private int dfs(boolean[] visit, int i, Map<Integer, List<Integer>> graph) {
        int count = 1;
        visit[i] = true;
        List<Integer> list = graph.get(i);
        if (list == null) return count;
        for (Integer p : list) {
            if (visit[p]) continue;
            count += dfs(visit, p, graph);
        }
        return count;
    }

    public int maxSubarraySumCircular(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        // 依旧是数组的最大子数组和的思路，这里需要环，因此，环状数组，需要将每个元素当做开头
        int n = nums.length;
        int pre = nums[0], res = nums[0];
        Deque<int[]> stack = new LinkedList<>();
        stack.add(new int[]{0, pre});
        for (int i = 1; i < 2 * n; i++) {
            // 维持至多n个长度
            while (!stack.isEmpty() && i - stack.peekFirst()[0] > n) {
                stack.pollFirst();
            }
            // 计算区间内的最大差值
            pre += nums[i % n];
            res = Math.max(pre - stack.peekFirst()[1], res);

            // 维持区间内的最小值
            while (!stack.isEmpty() && stack.peekLast()[1] >= pre) {
                stack.pollLast();
            }
            stack.addLast(new int[]{i, pre});
        }
        return res;
    }


    public int calculateMinimumHP(int[][] a) {
        if (a == null || a.length == 0 || a[0].length == 0) {
            return 0;
        }
        int row = a.length;
        int col = a[0].length;
        /*
        dp[i][j] 表示到达点（i，j)需要的最小点数，到达（i，j)可以从两个方向到达，上，左
        为了保证不死亡
        如果dn[i][j] <= 0 需要 a[i][j] + （dp[i - 1][j] or dp[i][j - 1]) = 1;
        如果dn[i][j] > 0 需要 dp

        dp[i - 1][j] || dp[i][j - 1]
        need[i][j] = a[i][j] >= 0? 1: (1 - a[i][j])
        上边 a[i - 1][j] 如果大于等于 need[i][j] 那么dp[i-1][j] = 1; 否则dp[i-1][j] = need - 1

        初始化
        dp[row-1][col-1] = need[i][j]
         */
        int[][] dp = new int[row][col];
        dp[row - 1][col - 1] = a[row - 1][col - 1] >= 0 ? 1 : 1 - (a[row - 1][col - 1]);

        for (int i = row - 1; i >= 0; i--) {
            for (int j = col - 1; j >= 0; j--) {
                if (i == row - 1 && j == col - 1) {
                    continue;
                }
                int need = a[i][j] >= 0 ? 1 : (1 - a[i][j]);

            }
        }

        return 0;
    }

    public int maxEnvelopes(int[][] envelopes) {
        // 排序，envelopes[i][j] 第二维度的 最长递增子序列
        if (envelopes == null || envelopes.length == 0 || envelopes[0].length == 0) {
            return 0;
        }
        int n = envelopes.length;
        Arrays.sort(envelopes, (a, b) -> a[0] - b[0]);

        int[] dp = new int[n];
        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (envelopes[j][1] >= envelopes[i][1]) {//最长上升子序列部分
                    continue;
                }
                if (envelopes[j][0] == envelopes[i][0]) {// 信封的宽高要严格小于
                    continue;
                }
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        int max = 0;
        for (int i : dp) {
            max = Math.max(i, max);
        }
        return max;
    }

    public int coinChange1(int[] coins, int amount) {
        if (coins == null || coins.length == 0) return -1;

        int[] dp = new int[amount + 1];
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            dp[i] = Integer.MAX_VALUE;
            for (int j = 0; j < coins.length; j++) {
                if (i >= coins[j] &&
                        dp[i - coins[j]] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }

    public List<TreeNode> generateTrees(int n) {

        if (n <= 0) {
            return new LinkedList<>();
        }

        return helper(1, n);

    }

    private List<TreeNode> helper(int start, int end) {
        List<TreeNode> allTrees = new LinkedList<>();
        if (start > end) {
            allTrees.add(null);
            return allTrees;
        }
        // 枚举可能得根节点
        for (int i = start; i <= end; i++) {

            List<TreeNode> leftTrees = helper(start, i - 1);
            List<TreeNode> rightTrees = helper(i + 1, end);

            for (TreeNode leftTree : leftTrees) {
                for (TreeNode rightTree : rightTrees) {

                    TreeNode curNode = new TreeNode(i);

                    curNode.left = leftTree;
                    curNode.right = rightTree;
                    allTrees.add(curNode);
                }
            }
        }
        return allTrees;
    }


    // TODO
    public int[] findPeakGrid(int[][] mat) {
        if (mat == null || mat.length == 0 || mat[0].length == 0) {
            return new int[2];
        }

        int row = mat.length;
        int col = mat[0].length;
        int i = 0, j = row - 1;
        for (; i <= j; i++) {

            int peekIdx = findPeekIdx(mat[i]);
            if (i == row - 1 && mat[i][peekIdx] > mat[i][peekIdx - 1]) {
                return new int[]{i, peekIdx};
            }

            int l = i, r = j;
            int peekCol = -1;
            while (l + 1 < r) {

                if (mat[i][peekIdx] > mat[i][peekIdx + 1]) {
                    r = peekIdx;
                } else if (mat[i][peekIdx] < mat[i][peekIdx + 1]) {
                    l = peekIdx;
                } else {
                    return new int[]{i, peekIdx};
                }
            }

        }

        return null;
    }

    private int findPeekIdx(int[] arr) {
        int l = 0, r = arr.length - 1;
        while (l + 1 < r) {
            int mid = l + ((r - l) >> 1);
            // 这里为什么可以和mid + 1比较，而不越界
            // (0,1) mid = 0 ; (0,1,2) mid = 1，所有ok
            if (arr[mid] < arr[mid + 1]) {
                l = mid;
            } else if (arr[mid] > arr[mid + 1]) {
                r = mid;
            } else {
                return mid;
            }
        }
        if (arr[l] < arr[r]) return r;
        return l;
    }

    private boolean check(int[] arr, int j, int cnt, int total) {
        if (cnt < total) return true;
        if (cnt == total && j < arr.length && arr[j] >= 0) return true;
        return false;
    }

    public int visiblePoints(List<List<Integer>> points, int angle, List<Integer> location) {
        List<Double> angleList = new ArrayList<>(points.size());
        for (List<Integer> point : points) {

        }
        return 0;
    }

    private void discard(Map<Integer, Integer> map, PriorityQueue<Integer> heap) {
        if (heap.isEmpty()) return;
        Integer tmp;
        while ((tmp = map.get(heap.peek())) != null && tmp > 0) {
            map.put(heap.peek(), tmp - 1);
            heap.poll();
        }
    }


    static List<Integer> single = Arrays.asList(0, 1, 8);
    static List<Integer> list = Arrays.asList(0, 1, 6, 8, 9);

    public boolean isStrobogrammatic(String num) {
        // write your code here
        if (num == null || num.length() == 0) {
            return false;
        }
        int i = 0, j = num.length() - 1;
        char[] nc = num.toCharArray();
        while (i < j) {
            int vi = nc[i] - '0';
            int vj = nc[j] - '0';
            if (map[vi] == -1 || map[vj] == -1) {
                return false;
            }
            if (map[vi] == map[vj] || map[vi] == vj || map[vj] == vi) {
                i++;
                j--;
            }
        }
        if (i == j) {
            int tmp = nc[i] - '0';
            return tmp == 0 || tmp == 1 || tmp == 8;
        }
        return true;
    }

    static int[] map = new int[]{
            0, 1, -1, -1, -1, -1, 9, -1, 8, 6
    };
    static int[][] map_2 = new int[][]{
            {0, 0}, {1, 1}, {2, -1}, {3, -1}, {4, -1},
            {5, -1}, {6, 9}, {7, -1}, {8, 8}, {9, 6},
    };

    /*
    输入：mat = [[1,2,3],[4,5,6],[7,8,9]]
    输出：[1,2,4,7,5,3,6,8,9]
     */
    public int[] findDiagonalOrder(int[][] mat) {
        if (mat == null || mat.length == 0 || mat[0].length == 0) {
            return new int[0];
        }
        int row = mat.length, col = mat[0].length;
        int[] res = new int[row * col];
        int idx = 0;
        int i = 0, j = 0;
        int len = row + col - 1;
        for (int d = 0; d < len; d++) {
            if ((d & 1) == 0) {// 偶数，从下到上遍历
                i = d < row ? d : row - 1;
                j = d < row ? 0 : (d - row + 1);
                while (i >= 0 && j < col) {
                    res[idx++] = mat[i][j];
                    i--;
                    j++;
                }
            } else {// 奇数，从上到下遍历
                i = d < col ? 0 : d - col + 1;
                j = d < col ? d : col - 1;
                while (i < row && j >= 0) {
                    res[idx++] = mat[i][j];
                    i++;
                    j--;
                }
            }
        }
        return res;
    }

    public int lengthOfLongestSubstringTwoDistinct(String s) {
        // Write your code here
        if (s == null) return 0;
        if (s.length() <= 1) return s.length();
        int n = s.length(), k = 2;
        int[] map = new int[256];
        int cnt = 0, ans = 0;
        char c = ' ';
        for (int i = 0, j = 0; i < n; i++) {
            while (j < n && check(j, s, map, cnt, k)) {
                c = s.charAt(j);
                if (map[c] == 0) {
                    cnt++;
                }
                map[c]++;
                j++;
            }
            if (cnt >= k || j == n) {
                ans = Math.max(ans, j - i);
                c = s.charAt(i);
                map[c]--;
                if (map[c] == 0) {
                    cnt--;
                }
            }
        }
        return ans;
    }

    private boolean check(int idx, String s, int[] map, int cnt, int limit) {
        char c = s.charAt(idx);
        if (map[c] == 0 && cnt + 1 > limit) {
            return false;
        }
        return true;
    }

    public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
        if (customers == null || grumpy == null || customers.length != grumpy.length) {
            return 0;
        }
        int n = customers.length;
        int ans = 0;
        for (int i = 0; i < customers.length; i++) {
            if (grumpy[i] == 0) {
                ans += customers[i];
            } else {
                grumpy[i] = customers[i];
            }
        }

        int save = 0;
        for (int i = 0; i < minutes; i++) {
            save += customers[i];
        }
        int max = save;
        for (int i = minutes; i < n; i++) {
            save += grumpy[i];
            save -= grumpy[i - minutes];
            if (max < save) max = save;
        }

        return ans + max;
    }

    /*
    customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3
    输出：16
     */
    public int maxSatisfied_ii(int[] customers, int[] grumpy, int minutes) {
        if (customers == null || grumpy == null || customers.length != grumpy.length) {
            return 0;
        }
        int n = customers.length;
        int[] preSum = new int[n + 1];
        for (int i = 0; i < n; i++) {
            preSum[i + 1] = preSum[i] + customers[i];
        }
        if (minutes >= n) {
            return preSum[n];
        }

        int i = 0, j = 0;
        int ans = 0;
        boolean start1 = false;
        while (i < n) {

            int preSum0 = 0;
            while (i < n && !start1 && grumpy[i] == 0) {
                preSum0 += customers[i];
                i++;
            }
            start1 = true;
            int cnt = 0;
            j = i;
            while (j < n && cnt < minutes) {
                j++;
                cnt++;
            }
            if (cnt == minutes)
                ans = Math.max(preSum0 + preSum[j] - preSum[j - cnt], ans);
            while (i < j && cnt > 0) {
                if (grumpy[i] == 1) {
                    start1 = false;
                    i++;
                    cnt--;
                    continue;
                }
                if (!start1 && grumpy[i] == 0) {
                    break;
                }
                i++;
            }
        }
        return ans;
    }

    private static void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

